package org.lql.algo.codecrush.hot100.heap;

import java.util.Random;

/**
 * @author: liangqinglong
 * @date: 2025-09-16 20:53
 * @description: 215. 数组中的第K个最大元素 <a href="https://leetcode.cn/problems/kth-largest-element-in-an-array/description/?envType=study-plan-v2&envId=top-100-liked">...</a>
 **/
public class FindKthLargest {

	public int findKthLargest(int[] nums, int k) {
		return quickSort(nums, 0, nums.length - 1, nums.length - k);
	}

	public int quickSort(int[] arr, int l, int r, int index) {
		if (l >= r) {
			return arr[l];
		}
		int pivot = partition(arr, l, r);
		if (index <= pivot) {
			return quickSort(arr, l, pivot, index);
		} else {
			return quickSort(arr, pivot + 1, r, index);
		}
	}

	public int partition(int[] arr, int l, int r) {
		int pivot = new Random().nextInt(r - l + 1);
		int pivotVal = arr[l + pivot];
		while (l <= r) {
			while (arr[l] < pivotVal) {
				l++;
			}
			while (arr[r] > pivotVal) {
				r--;
			}
			if (l == r) {
				break;
			}
			if (l < r) {
				int tmp = arr[l];
				arr[l] = arr[r];
				arr[r] = tmp;
				l++;
				r--;
			}
		}
		return r;
	}

	public static void main(String[] args) {
		int[] nums = {3, 2, 1, 5, 6, 4};
		int k = 2;
		int kthLargest = new FindKthLargest().findKthLargest(nums, k);
		System.out.println(kthLargest);
	}

}
